UVa/11662 - Triangular Grid/11662.cpp

   1 #include <iostream>
   2 #include <cmath>
   3 #include <cstdlib>
   4 #include <algorithm>
   5 #include <cassert>
   6 #include <cstdio>
   7
   8 using namespace std;
   9
  10 int B, H;
  11
  12 int myFloor(int a, int b) {
  13         if ((a < 0) ^ (b < 0)) { // negative
  14                 return -(abs(a)/abs(b)) - 1;
  15         } else {
  16                 return abs(a)/abs(b);
  17         }
  18 }
  19
  20 int mod(int a, int b) {
  21         return (a % b + b) % b;
  22 }
  23
  24 int Kh(int x, int y) {
  25         return myFloor(y, H);
  26 }
  27
  28 int Ka(int x, int y) {
  29         return myFloor(2*H*x - B*y, 2*H*B);
  30 }
  31
  32 int Kv(int x, int y) {
  33         return myFloor(2*H*x + B*y, 2*H*B);
  34 }
  35
  36 bool isVertex(int x, int y) {
  37     assert(B % 2 == 0);
  38         if (mod(y, H) != 0) return false;
  39         int q = y / H;
  40         if (q % 2 == 0) return mod(x, B) == 0;
  41         return mod(x, B) == (B/2);
  42 }
  43
  44
  45 int main() {
  46         int x1, y1, x2, y2;
  47         while (cin >> B >> H >> x1 >> y1 >> x2 >> y2) {
  48                 if (B == 0 and H == 0 and x1 == 0 and y1 == 0 and x2 == 0 and y2 == 0) break;
  49                 B *= 2;
  50         x1 *= 2;
  51         x2 *= 2;
  52
  53                 int ans = abs(Kh(x1, y1) - Kh(x2, y2)) + abs(Ka(x1, y1) - Ka(x2, y2)) + abs(Kv(x1, y1) - Kv(x2, y2));
  54                 ans++;
  55
  56                 int dx = x2 - x1;
  57                 int dy = y2 - y1;
  58                 int g = __gcd(abs(dx), abs(dy));
  59                 dx /= g; dy /= g;
  60
  61                 assert(!isVertex(x1, y1));
  62                 assert(!isVertex(x2, y2));
  63
  64                 int x = x1, y = y1;
  65                 while (x != x2 or y != y2) {
  66                         ans -= 2 * isVertex(x, y);
  67                         x += dx;
  68                         y += dy;
  69                 }
  70
  71                 cout << ans << endl;
  72         }
  73         return 0;
  74 }